/* 
* Authors: Stefan Bojarovski <bojarovski@gmail.com>
*		   Dmitry Lebedev <leeevd@gmail.com>
* June,	2011
*/

#include "max_clique.h"
#include "bron_kerbosch.h"

using namespace boost;

bron_kerbosch::bron_kerbosch(Graph * const g) 
{
	inGraph = g;
	number_of_elements = 0;
	numNodes = boost::num_vertices(*inGraph);
}

VertexSet & bron_kerbosch::get_maxClique() {
	return maxClique;
}

int bron_kerbosch::get_num_of_nodes() const
{
	return numNodes;
}


void bron_kerbosch::do_bron_kerbosch_BT()
{
	graph_traits<Graph>::vertex_iterator vi, vi_end;
	VertexSet st;
	st.push_back(0);
	compsub.push_back(0);

	// st contains all the vertices of the graph
	for(tie(vi, vi_end) = boost::vertices(*inGraph); vi != vi_end; ++vi)
	{
		st.push_back(*vi);
	}

	extend_BT(st, 0, st.size() - 1);
}

void bron_kerbosch::extend_BT(VertexSet& old, int not_end, int const cand_end) 
{
	VertexSet newSet;
	newSet.push_back(0);
	int fixp = 0;
	int pos = 0, p = 0, s = 0;

	// Minimum number of disconnections
	int min_num_of_dis = cand_end;
	// Number of disconnections
	int num_of_dis = 0;

	/* 
	* Look for the vertex that is connected to the maximum number of vertices, i.e.,
	* the minimum number of disconnections (Step 1)
	*/
	for(int i = 1; (i <= cand_end) && (min_num_of_dis != 0); i++) 
	{
		p = old.at(i);
		int count = 0;
		// Count disconnections
		for(int j =  not_end + 1; (j <= cand_end) && (count < min_num_of_dis); j++)
		{
			Edge ed;
			bool found;
			tie(ed, found) = boost::edge(p, old.at(j), *inGraph);

			if (!(found || (old.at(i) == old.at(j))))
			{
				count++;
				pos = j;  
				// Save position of potential candidate
			}

		}
		// Test whether vertex at position i in the stack has a minimum number of disconnections
		if(count < min_num_of_dis) 
		{
			fixp = p;
			min_num_of_dis = count;
			//int s;
			if(i <= not_end) 
				s = pos;
			else 
			{
				s = i;
				num_of_dis = 1; 
				//If fixed point initially chosen from candidates then number of disconnections will be preincreased by one 
			}
		}
	}
	// Backtracking cycle
	for(num_of_dis = min_num_of_dis + num_of_dis; num_of_dis >= 1; num_of_dis--) 
	{
		// Interchange
		p = old.at(s);
		old.at(s) = old.at(not_end + 1);
		old.at(not_end + 1) = p;
		int sel = old.at(not_end +1);

		// Fill new set not (Step 2)
		int newne = 0;
		for(int i = 1; i <= not_end; i++)
		{
			Edge ed;
			bool found;
			tie(ed, found) = boost::edge(sel, old.at(i), *inGraph);
			if(found)
			{
				newSet.push_back(old.at(i));
			}
		}
		newne = newSet.size() - 1;
		// Fill new set cand (Step 2)
		int newce = newne;
		for(int i =  not_end + 2; i <= cand_end; i++)
		{
			Edge ed;
			bool found;
			tie(ed, found) = boost::edge(sel, old.at(i), *inGraph);

			if(found)
			{
				newSet.push_back(old.at(i));
			}
		}
		newce = newSet.size() - 1;
		// The selected vertex is added to compsub (Step 3)
		compsub.push_back(sel);
		number_of_elements++;

		if(newce == 0) 
		{ 
			// Maximal clique found
			if(number_of_elements > bron_kerbosch::maxClique.size()) 
			{
				maxClique.clear();
				maxClique.insert(maxClique.begin(), compsub.begin() + 1, compsub.begin() + number_of_elements +1);
			}
		} 
		// Otherwise calls the extension operator to operate on the sets just formed  (Step 4)
		else 
		{ 
			if (newne < newce)
				extend_BT(newSet, newne, newce);
		}

		// Upon return removal of the selected candidate from compsub and its addition to the old set 'not' (Step 5)
		// Remove from compsub
		number_of_elements--;
		// Add to 'not'
		not_end++;

		// Select a candidate disconnected to the fixed point (Step 1)
		if(num_of_dis > 1) 
		{  
			s = not_end;
			Edge ed;
			bool found;
			do
			{
				s++;
				tie(ed, found) = boost::edge(fixp, old.at(s), *inGraph);
			}
			while(found);
		}
	}
	return;
}